//
// Created by zx208 on 2024/10/17.
//

// 请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。
// 要求：不得额外申请新的链结点。

// 思路： 首先要找到数据域最小的结点 那我们要先直接遍历一遍全链表
// 然后移动需要找到最小结点的前驱结点 和头指针 来进行操作

#include "../SingleLinkedList.h"

LinkedList Create_List_R(LinkedList head, int n){

    // 先创建头指针
    head = (LinkedList) malloc(sizeof( LNode));
    head->next = NULL;

    // 创建一个工作指针
    LinkedList node = head;

    for (int i = 0; i < n; ++i) {
        LinkedList p = (LinkedList) malloc(sizeof( LNode));
        int data;
        scanf(" %d", &data);
        p->data = data;
        p->next = node->next; // 即 p->next = NULL;
        node->next = p;
        node = p;
    }
    return head;
}

void PrintLL(LinkedList L){
    LNode *node = L->next;
    while(node){
        printf("%d ", node->data);
        node = node->next;
    }
}

Status Moving_Min_LL(LinkedList L){
    LinkedList p = L, tmp1, tmp2, minp;
    ElemType min_value = INT_MAX;
    while (p->next){
        if(p->next->data < min_value) minp = p, min_value = p->next->data;
        p = p->next;
    }
    tmp1 = L->next;
    tmp2 = minp->next->next;
    L->next = minp->next;
    minp->next->next = tmp1;
    minp->next = tmp2;
    return OK;
}

int main(void){
    LinkedList L = NULL;
    L = Create_List_R(L, 5);
    Moving_Min_LL(L);
    PrintLL(L);
    return 0;
}

// 2 5 1 4 3